//除自身以外数组的乘积
/*给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

*/
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> answer(nums.size(), 1);
        int left = 0;
        int right = nums.size() - 1;
        int lp = 1;
        int rp = 1;
        while (right >= 0 && left < nums.size()) {
            answer[right] *= rp;
            answer[left] *= lp;
            lp *= nums[left++];
            rp *= nums[right--];
        }
        return answer;
    }
};

//最大子数组和
/*给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组
是数组中的一个连续部分。
*/
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int quick = 0;
        int max = -100001;
        int sum = 0;
        while(quick < nums.size() && nums[quick] <= 0) {
            if (nums[quick] > max)
                max = nums[quick];
            quick++;
        }
        while (quick < nums.size()) {
            sum += nums[quick];
            if (sum <= 0) {
                sum = 0;
            }
            if (max < sum) {
                max = sum;
            }
            quick++;
        }
        return max;
    }
};



//螺旋矩阵 II
/*给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
1 <= n <= 20
*/
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> arr;
        for (int i = 0; i < n; i++) {
            vector<int> nums;
            for (int j = 0; j < n; j++) {
                nums.push_back(0);
            }
            arr.push_back(nums);
        }
        int state = 1;
        int x = 0;
        int y = 0;
        int count = 1;
        do {
            if (state == 1) {
                arr[x][y] = count;
                if (y + 1 >= n || arr[x][y + 1] != 0) {
                    state = 2;
                } else {
                    count++;
                    y++;
                }
            } else if (state == 2) {
                arr[x][y] = count;
                if (x + 1 >= n || arr[x + 1][y] != 0) {
                    state = 3;
                } else {
                    count++;
                    x++;
                }
            } else if (state == 3) {
                arr[x][y] = count;
                if (y - 1 < 0 || arr[x][y - 1] != 0) {
                    state = 4;
                } else {
                    count++;
                    y--;
                }
            } else if (state == 4) {
                arr[x][y] = count;
                if (x - 1 < 0 || arr[x - 1][y] != 0) {
                    state = 1;
                } else {
                    count++;
                    x--;
                }
            }
        } while (count != n * n);
        arr[x][y] = count;
        return arr;
    }
};
